{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<script>\n",
       "code_show=true; \n",
       "function code_toggle() {\n",
       " if (code_show){\n",
       " $('div.input').hide();\n",
       " } else {\n",
       " $('div.input').show();\n",
       " }\n",
       " code_show = !code_show\n",
       "} \n",
       "$( document ).ready(code_toggle);\n",
       "</script>\n",
       "<form action=\"javascript:code_toggle()\"><input type=\"submit\" value=\"Click here to toggle on/off the raw code for QISKit exercises.\"></form>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import HTML\n",
    "\n",
    "HTML('''<script>\n",
    "code_show=true; \n",
    "function code_toggle() {\n",
    " if (code_show){\n",
    " $('div.input').hide();\n",
    " } else {\n",
    " $('div.input').show();\n",
    " }\n",
    " code_show = !code_show\n",
    "} \n",
    "$( document ).ready(code_toggle);\n",
    "</script>\n",
    "<form action=\"javascript:code_toggle()\"><input type=\"submit\" value=\"Click here to toggle on/off the raw code for QISKit exercises.\"></form>''')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 6. First quantum algorithms\n",
    "\n",
    "In this chapter, we will review the first quantum algorithms which initiated the field of quantum computing. These algorithms were worked out explicitly for the purpose of showing that there could be an advantage in using a quantum computer, rather than a classical one, to compute the solution to certain problems. Starting from Deutsch algorithm, which shows that a quantum computer can solve a problem in half the steps of a classical one. Going to Bernstein-Vazirani algorithm, where a linear speed-up for the specific problem solved was obtained. Ending with Simon's algorithm, which showed that there can be an exponential gain in the number of steps needed to solve another particular problem if a quantum computer is used instead of a classical one.\n",
    "Let us now look more deeply in the problems that these algorithms solve and how they do it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.1 Deutsch’s algorithm\n",
    "\n",
    "The Deutsch algorithm was the first example of a quantum algorithm which performs better than the best classical algorithm. It showed that there can be advantages in using a quantum computer as a computational tool for a specific problem.\n",
    "\n",
    "Deutsch Algorithm solves the following problem: suppose that you are given a functions $f: \\{0,1\\} \\rightarrow \\{0,1\\} $ which takes $0$ or $1$ as input and outputs $0$ or $1$. The function itself can be as complicated as needed, the only requirement is that it takes a bit as input and outputs another bit. Given two different inputs $x$ and $y$, check if the function $f(x)$ is equal to $f(y)$.\n",
    "\n",
    "Let us first see how the classical algorithm solves the problem. The best way to do this classically is to evaluate $f(x)$ and $f(y)$ separately and then compare the results. This requires at least two calls to the function $f$, therefore we classify the solution as having complexity $2$.\n",
    "\n",
    "Let us take a look at a quantum algorithm which can solve the problem in only one step! The quantum circuit which implements the algorithm is the following \n",
    "\n",
    "<img src=\"figures/5/deutsch2.jpeg\"  width=\"300\">\n",
    "$$\\text{1. Quantum circuit for Deutsch's algorithm.}$$\n",
    "\n",
    "Where H are Hadamard gates and $\\text{Q}_f$ is the query function described by the action on a qubit $\\lvert x \\rangle$ as\n",
    "$$ \\lvert x \\rangle \\rightarrow (-1)^{f(x)} \\lvert x \\rangle $$\n",
    "\n",
    "Now, let us go through the steps of the Deutsch algorithm:\n",
    "\n",
    "<ol>\n",
    "    <li> The input qubit is initialized to the zero state \n",
    "    $$\\lvert \\psi_1 \\rangle = \\lvert 0 \\rangle $$ </li>\n",
    "    <li> Apply Hadamard on the qubit to get the state $$\\lvert \\psi_2 \\rangle = \\frac{1}{\\sqrt{2}} \\left(\\lvert 0 \\rangle + \\lvert 1 \\rangle \\right)  $$ </li>\n",
    "    <li> We make a query $\\text{Q}_f$, \n",
    "    $$ \\lvert \\psi_3 \\rangle = \\frac{1}{\\sqrt{2}} \\left( (-1)^{f(0)} \\lvert 0 \\rangle + (-1)^{f(1)} \\lvert 1 \\rangle \\right)  $$ \n",
    "    Thus, if $f(0) = f(1)$, (up to a global phase factor):\n",
    "    $$ \\lvert \\psi_3 \\rangle = \\frac{(-1)^{f(0)}}{\\sqrt{2}} \\left(  \\lvert 0 \\rangle + \\lvert 1 \\rangle \\right) $$\n",
    "    \n",
    "    while if $f(0) \\neq f(1)$, (up to a global phase factor):\n",
    "    $$ \\lvert \\psi_3 \\rangle = \\frac{(-1)^{f(0)}}{\\sqrt{2}} \\left(  \\lvert 0 \\rangle - \\lvert 1 \\rangle \\right) $$\n",
    "    </li>\n",
    "    \n",
    "    <li> Apply Hadamard again. If  $f(0) = f(1)$:\n",
    "        $$ \\lvert \\psi_4 \\rangle = (-1)^{f(0)} \\lvert 0 \\rangle $$\n",
    "        \n",
    "        while if  $f(0) \\neq f(1)$:\n",
    "        $$ \\lvert \\psi_4 \\rangle = (-1)^{f(0)} \\lvert 1 \\rangle $$\n",
    "    </li>\n",
    "    <li> Measuring the qubit will either give:\n",
    "        $$ \"0\", \\; \\; \\text{if} \\; f(0) = f(1)$$\n",
    "    \n",
    "        $$ \"1\", \\; \\; \\text{if} \\; f(0) \\neq f(1)$$\n",
    "    </li>\n",
    "</ol>\n",
    "\n",
    "Therefore by looking at the value of the measured qubit, we can tell whether $f(x) = f(y)$ or $f(0) \\neq f(1)$, solving the problem with only one query to the function $\\text{Q}_f$.\n",
    "\n",
    "Compared to the classical algorithm, the quantum algorithm takes half the number of steps! This might not seem much of an advantage but it is a first steps in proving the usefulness of quantum computation.\n",
    "Also, if the input to the function is not just one bit but an $n$ bit string, it can be proven that the quantum algorithm will take $\\frac{n}{2}$ queries to the function (just run the algorithm on pair of bits) rather the $n$ steps needed for a classical algorithm.\n",
    "\n",
    "### Example\n",
    "\n",
    "In [4], the Deutsch algorithm was implemented on a real device. However, in order to do it two qubits were used, one is used as ancilla. In this way, the query function $Q_f$ was realized. Let us see how it works\n",
    "\n",
    "<img src=\"figures/5/deutsch_ex1.jpeg\"  width=\"300\">\n",
    "\n",
    "<ol>\n",
    "    <li> The first qubit is initialized to zero and the second is initialized to one \n",
    "    $$\\lvert \\psi_1 \\rangle = \\lvert 0\\rangle \\lvert 1 \\rangle_a $$ </li>\n",
    "    <li> Apply Hadamard on both qubits $$\\lvert \\psi_2 \\rangle = \\frac{1}{\\sqrt{2}} \\left(\\lvert 0 \\rangle + \\lvert 1 \\rangle \\right) \\frac{1}{\\sqrt{2}} \\left(\\lvert 0 \\rangle_a - \\lvert 1 \\rangle_a \\right) = \\frac{1}{2}\\left(\\lvert 0 \\rangle \\lvert 0 \\rangle_a  - \\lvert 0 \\rangle \\lvert 1 \\rangle_a + \\lvert 1 \\rangle \\lvert 0 \\rangle_a - \\lvert 1 \\rangle \\lvert 1 \\rangle_a \\right)   $$ </li>\n",
    "    <li> The query function $\\text{Q}_f$ can be implemented in different ways. Let us consider the case where $f(0) = 0$ and $f(1)=1$, thus $Q_f = CX_{12}$ \n",
    "    $$ \\lvert \\psi_3 \\rangle = \\frac{1}{2} \\left(\\lvert 0 \\rangle \\lvert 0 \\oplus 0 \\rangle_a  - \\lvert 0 \\rangle \\lvert 1 \\oplus 0 \\rangle_a + \\lvert 1 \\rangle \\lvert 0 \\oplus 1 \\rangle_a - \\lvert 1 \\rangle \\lvert 1 \\oplus 1 \\rangle_a \\right) = \\frac{1}{2}\\left(\\lvert 0 \\rangle \\lvert 0 \\rangle_a  - \\lvert 0 \\rangle \\lvert 1 \\rangle_a + \\lvert 1 \\rangle \\lvert 1 \\rangle_a - \\lvert 1 \\rangle \\lvert 0 \\rangle_a \\right)  $$ \n",
    "    Thus:\n",
    "    $$ \\lvert \\psi_3 \\rangle = \\frac{1}{\\sqrt{2}} \\left(\\lvert 0 \\rangle - \\lvert 1 \\rangle \\right) \\frac{1}{\\sqrt{2}} \\left(\\lvert 0 \\rangle_a - \\lvert 1 \\rangle_a \\right) $$\n",
    "    \n",
    "    \n",
    "    <li> Apply Hadamard on both qubits again:\n",
    "        $$ \\lvert \\psi_4 \\rangle = \\lvert 1 \\rangle \\lvert 1 \\rangle_a $$\n",
    "    </li>\n",
    "    \n",
    "    <li> Measuring the first qubit will give $\"1\"$, therefore $ f(0) \\neq f(1)$\n",
    "    \n",
    "    </li>\n",
    "</ol>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\"> QISKit: implement the example of Deutsch algorithm </span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### <span style=\"color:blue\"> 1) Use the query function $Q_f=CX_{12}$ </span>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "List of gates:\n",
      "x\n",
      "h\n",
      "h\n",
      "cx\n",
      "h\n",
      "h\n",
      "measure\n",
      "\n",
      "The measured outcomes of the circuits are: {'1': 1024}\n"
     ]
    }
   ],
   "source": [
    "from initialize import *\n",
    "\n",
    "\n",
    "#initialize quantum program\n",
    "my_alg = initialize(circuit_name = 'deutsch', qubit_number=2, bit_number=1, backend = 'local_qasm_simulator', shots = 1024)\n",
    "\n",
    "#add gates to the circuit\n",
    "my_alg.q_circuit.x(my_alg.q_reg[1]) # initializes ancilla qubit\n",
    "\n",
    "my_alg.q_circuit.h(my_alg.q_reg[0]) # applies H gate to first qubit\n",
    "my_alg.q_circuit.h(my_alg.q_reg[1]) # applies H gate to second qubit\n",
    "\n",
    "my_alg.q_circuit.cx(my_alg.q_reg[0],my_alg.q_reg[1]) ## applies CX gate as the query function\n",
    "\n",
    "my_alg.q_circuit.h(my_alg.q_reg[0]) # applies H gate to first qubit\n",
    "my_alg.q_circuit.h(my_alg.q_reg[1]) # applies H gate to second qubit \n",
    "\n",
    "my_alg.q_circuit.measure(my_alg.q_reg[0], my_alg.c_reg[0]) # measures the first qubit and store the result in the first bit\n",
    "\n",
    "print('List of gates:')\n",
    "for circuit in my_alg.q_circuit:\n",
    "    print(circuit.name)\n",
    "\n",
    "#Execute the quantum algorithm\n",
    "result = my_alg.Q_program.execute(my_alg.circ_name, backend=my_alg.backend, shots= my_alg.shots)\n",
    "\n",
    "#Show the results obtained from the quantum algorithm \n",
    "counts = result.get_counts(my_alg.circ_name)\n",
    "\n",
    "print('\\nThe measured outcomes of the circuits are:',counts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.2 The Bernstein-Vazirani algorithm\n",
    "\n",
    "The second quantum algorithm which shows a quantum speed-up is the Bernstein-Vazirani algorithm. The algorithm solves the following problem: given a function $f: \\{0,1\\}^n \\rightarrow \\{0,1\\} $ which takes an $n$ bit string as input and outputs a single bit and has some structure. That is, there is a secret $n$ bit string $s \\in \\{0,1\\}^n$ which determines $f$. In particular, for an input $x$, $f(x) = s \\cdot x \\, \\text{(mod 2)}$. Find $s$.\n",
    "\n",
    "To find $s$ classically, we would have to call the function $f(x)$ $n$ times, each time determining one of the bits of $s$.\n",
    "\n",
    "On the other side, a quantum algorithm can solve the problem in only one step! giving a polynomial speed-up with respect to the classical algorithm. Let us see the quantum circuit which implements the corresponding algorithm.\n",
    "\n",
    "<img src=\"figures/5/vazirani1.jpeg\" width=\"300\">\n",
    "$$\\text{2. Quantum circuit for the Bernstein-Vazirani algorithm}$$\n",
    "\n",
    "Where $\\text{Q}_f$ is the same query function as for the Deutsch algorithm, but now acting on $n$ qubits:\n",
    "$$ \\lvert x \\rangle \\rightarrow (-1)^{f(x)} \\lvert x \\rangle $$\n",
    "\n",
    "The algorithm proceeds as follows\n",
    "\n",
    "<ol>\n",
    "    <li> The input register is initialized to the zero state \n",
    "    $$\\lvert \\psi_1 \\rangle = \\lvert 0 \\rangle^{\\otimes n} $$ </li>\n",
    "    \n",
    "    <li> Apply Hadamard on all qubits to get a uniform superposition of all $n$-bit strings \n",
    "    $$\\lvert \\psi_2 \\rangle = \\frac{1}{\\sqrt{2^n}} \\sum_{x \\in \\{0,1\\}^{n} } \\lvert x \\rangle  $$ </li>\n",
    "    \n",
    "    <li> We make a query $\\text{Q}_f$, \n",
    "    $$ \\lvert \\psi_3 \\rangle = \\frac{1}{\\sqrt{2^n}} \\sum_{x \\in \\{0,1\\}^{n} } (-1)^{f(x)} \\lvert x \\rangle = \\\\\n",
    "    = \\frac{1}{\\sqrt{2^n}} \\sum_{x \\in \\{0,1\\}^{n} } (-1)^{s_1 \\cdot x_1} ... (-1)^{s_n \\cdot x_n} \\lvert x \\rangle = \\\\\n",
    "    = \\frac{\\lvert 0 \\rangle + (-1)^{s_1} \\lvert 1 \\rangle }{\\sqrt{2}} \\otimes ... \\otimes \\frac{\\lvert 0 \\rangle + (-1)^{s_n} \\lvert 1 \\rangle }{\\sqrt{2}}   $$\n",
    "    \n",
    "    </li>\n",
    "    \n",
    "    <li> Apply Hadamard on all qubits\n",
    "    \n",
    "        $$ \\lvert \\psi_4 \\rangle = \\lvert s_1 \\rangle ... \\lvert s_n \\rangle $$\n",
    "    </li>\n",
    "    <li> Measuring all $n$ qubits will give the secret $n$-bit string $s$\n",
    "    </li>\n",
    "</ol>\n",
    "\n",
    "As mentioned above, the quantum algorithm provides a polynomial speed-up against the best classical algorithm. Although the problem still feels like it is purposely designed so that it will be easier to solve on a quantum computer, at the time it was quite an achievement to prove that such a speed-up was even possible.\n",
    "\n",
    "### Example \n",
    "\n",
    "An example of realization of the Bernstein-Vazirani algorithm can be found in [7]. Again, the algorithm makes use of an ancilla qubit to implement the query function $Q_f$. Let us see the steps of the algorithm for $n=2$ qubits and a secret string $s=11$\n",
    "\n",
    "<img src=\"figures/5/vazirani_ex1.jpeg\"  width=\"300\">\n",
    "\n",
    "<ol>\n",
    "    <li> The input registers are initialized to zero and the ancilla qubit to one \n",
    "    $$\\lvert \\psi_1 \\rangle = \\lvert 0 0 \\rangle \\lvert 1 \\rangle_a $$ </li>\n",
    "    \n",
    "    <li> Apply Hadamard on all qubits\n",
    "    $$\\lvert \\psi_2 \\rangle = \\frac{1}{2} \\left( \\lvert 0 0 \\rangle + \\lvert 0 1 \\rangle + \\lvert 1 0 \\rangle + \\lvert 1 1 \\rangle \\right) \\frac{1}{\\sqrt{2}} \\left( \\lvert 0 \\rangle_a - \\lvert 1 \\rangle_a \\right)  $$ </li>\n",
    "    \n",
    "    <li> For the string $s=11$, the query function can be implemented as $\\text{Q}_f = CX_{1a}CX_{2a}$, \n",
    "    $$ \\lvert \\psi_3 \\rangle = \\frac{1}{2\\sqrt{2}} \\left[ \\lvert 0 0 \\rangle \\left( \\lvert 0 \\oplus 0 \\oplus 0 \\rangle_a - \\lvert 1 \\oplus 0 \\oplus 0 \\rangle_a \\right)+ \\lvert 0 1 \\rangle  \\left( \\lvert 0 \\oplus 0 \\oplus 1 \\rangle_a - \\lvert 1 \\oplus 0 \\oplus 1 \\rangle_a \\right) + \\lvert 1 0 \\rangle  \\left( \\lvert 0 \\oplus 1 \\oplus 0 \\rangle_a - \\lvert 1 \\oplus 1 \\oplus 0 \\rangle_a \\right) + \\lvert 1 1 \\rangle  \\left( \\lvert 0 \\oplus 1 \\oplus 1 \\rangle_a - \\lvert 1 \\oplus 1 \\oplus 1 \\rangle_a \\right)  \\right] $$\n",
    "    \n",
    "    Thus\n",
    "    $$ \\lvert \\psi_3 \\rangle = \\frac{1}{2\\sqrt{2}} \\left[ \\lvert 0 0 \\rangle \\left( \\lvert 0 \\rangle_a - \\lvert 1 \\rangle_a \\right) - \\lvert 0 1 \\rangle  \\left( \\lvert 0 \\rangle_a - \\lvert  1 \\rangle_a \\right) - \\lvert 1 0 \\rangle  \\left( \\lvert 0  \\rangle_a - \\lvert 1 \\rangle_a \\right) + \\lvert 1 1 \\rangle  \\left( \\lvert 0 \\rangle_a - \\lvert 1 \\rangle_a \\right)  \\right] \\\\\n",
    "   = \\frac{1}{2} \\left( \\lvert 0 0 \\rangle - \\lvert 0 1 \\rangle - \\lvert 1 0 \\rangle + \\lvert 1 1 \\rangle \\right) \\frac{1}{\\sqrt{2}} \\left( \\lvert 0 \\rangle_a - \\lvert 1 \\rangle_a \\right)  \\\\\n",
    "    = \\frac{1}{\\sqrt{2}} \\left( \\lvert 0 \\rangle - \\lvert 1 \\rangle \\right)\\frac{1}{\\sqrt{2}} \\left( \\lvert 0 \\rangle - \\lvert 1 \\rangle \\right)\\frac{1}{\\sqrt{2}} \\left( \\lvert 0 \\rangle_a - \\lvert 1 \\rangle_a \\right)$$\n",
    "    \n",
    "    </li>\n",
    "    \n",
    "    <li> Apply Hadamard on all qubits\n",
    "    \n",
    "        $$ \\lvert \\psi_4 \\rangle = \\lvert 1 \\rangle \\lvert 1 \\rangle \\lvert 1 \\rangle $$\n",
    "    </li>\n",
    "    <li> Measuring the first two qubits will give the secret $2$-bit string $s = 11$\n",
    "    </li>\n",
    "</ol>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\"> QISKit: implement the example of the Bernstein-Vazirani algorithm </span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### <span style=\"color:blue\"> 2) Use the query function $Q_f=CX_{23}CX_{13}$ </span>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "List of gates:\n",
      "x\n",
      "h\n",
      "h\n",
      "h\n",
      "cx\n",
      "cx\n",
      "h\n",
      "h\n",
      "h\n",
      "measure\n",
      "measure\n",
      "\n",
      "The measured outcomes of the circuits are: {'11': 1024}\n"
     ]
    }
   ],
   "source": [
    "from initialize import *\n",
    "\n",
    "\n",
    "#initialize quantum program\n",
    "my_alg = initialize(circuit_name = 'ber_vaz', qubit_number=3, bit_number=2, backend = 'local_qasm_simulator', shots = 1024)\n",
    "\n",
    "#add gates to the circuit\n",
    "my_alg.q_circuit.x(my_alg.q_reg[2]) # initializes ancilla qubit\n",
    "\n",
    "my_alg.q_circuit.h(my_alg.q_reg[0]) # applies H gate to first qubit\n",
    "my_alg.q_circuit.h(my_alg.q_reg[1]) # applies H gate to second qubit\n",
    "my_alg.q_circuit.h(my_alg.q_reg[2]) # applies H gate to third qubit\n",
    "\n",
    "my_alg.q_circuit.cx(my_alg.q_reg[1],my_alg.q_reg[2]) ## applies CX gate as the query function\n",
    "my_alg.q_circuit.cx(my_alg.q_reg[0],my_alg.q_reg[2]) ## applies CX gate as the query function\n",
    "\n",
    "my_alg.q_circuit.h(my_alg.q_reg[0]) # applies H gate to first qubit\n",
    "my_alg.q_circuit.h(my_alg.q_reg[1]) # applies H gate to second qubit \n",
    "my_alg.q_circuit.h(my_alg.q_reg[2]) # applies H gate to third qubit\n",
    "\n",
    "my_alg.q_circuit.measure(my_alg.q_reg[0], my_alg.c_reg[0]) # measures the first qubit and store the result in the first bit\n",
    "my_alg.q_circuit.measure(my_alg.q_reg[1], my_alg.c_reg[1]) # measures the second qubit and store the result in the second bit\n",
    "\n",
    "print('List of gates:')\n",
    "for circuit in my_alg.q_circuit:\n",
    "    print(circuit.name)\n",
    "\n",
    "#Execute the quantum algorithm\n",
    "result = my_alg.Q_program.execute(my_alg.circ_name, backend=my_alg.backend, shots= my_alg.shots)\n",
    "\n",
    "#Show the results obtained from the quantum algorithm \n",
    "counts = result.get_counts(my_alg.circ_name)\n",
    "\n",
    "print('\\nThe measured outcomes of the circuits are:',counts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.3 Simon's algorithm\n",
    "\n",
    "Simon's algorithm was the first quantum algorithm to show an exponential speed-up versus the best classical algorithm in solving a specific problem. This inspired the quantum algorithm for the discrete Fourier transform, also known as quantum Fourier transform, which is used in the most famous quantum algorithm: Shor's factoring algorithm.\n",
    "\n",
    "Simon's algorithm solves the following problem: given a function $f: \\{0,1\\}^n \\rightarrow \\{0,1\\}^n $ which takes an $n$ bit string as input and outputs another $n$-bit string and has some secret structure $s\\in\\{0,1\\}^n$ and $s\\neq 0^{\\otimes n}$ such that given two different inputs $x$ and $y$, $f(x) = f(y)$ if and only if $y = x + s \\, \\text{mod 2}$. Find $s$.\n",
    "\n",
    "Classically, if the algorithms picks inputs at random it will learn when $f(x_i) = f(x_j)$ so that $s=x_i \\oplus x_j$ (where $\\oplus$ stands for \"bit-wise addition modulo 2\"). Each pair determines a bit of $s$, therefore we need to find $n$ pairs to discover the value of $s$. It can be shown that $\\approx 2^{\\frac{n}{2}}$ calls of $f$ are necessary to find $s$ with a classical algorithm.\n",
    "\n",
    "The quantum algorithm allows to find $s$ in $\\approx n$ calls to the function $f$. Let's see how\n",
    "\n",
    "<img src=\"figures/5/simon1.jpeg\"  width=\"300\">\n",
    "$$\\text{3. Quantum circuit for Simon's algorithm}$$\n",
    "\n",
    "Where $\\text{Q}_f$ acts on two quantum registers as:\n",
    "$$ \\lvert x \\rangle \\lvert 0 \\rangle \\rightarrow \\lvert x \\rangle \\lvert f(x) \\rangle $$\n",
    "\n",
    "The algorithm involves the following steps\n",
    "<ol>\n",
    "    <li> Two $n$-qubit input registers are initialized to the zero state \n",
    "    $$\\lvert \\psi_1 \\rangle = \\lvert 0 \\rangle^{\\otimes n} \\lvert 0 \\rangle^{\\otimes n} $$ </li>\n",
    "    \n",
    "    <li> Apply Hadamard on the first register\n",
    "    $$\\lvert \\psi_2 \\rangle = \\frac{1}{\\sqrt{2^n}} \\sum_{x \\in \\{0,1\\}^{n} } \\lvert x \\rangle\\lvert 0 \\rangle^{\\otimes n}  $$ </li>\n",
    "    \n",
    "    <li> We make a query $\\text{Q}_f$, \n",
    "    $$ \\lvert \\psi_3 \\rangle = \\frac{1}{\\sqrt{2^n}} \\sum_{x \\in \\{0,1\\}^{n} } \\lvert x \\rangle \\lvert f(x) \\rangle  $$\n",
    "    \n",
    "    </li>\n",
    "    \n",
    "     <li> We measure the second register. A certain value of $f(x)$ will be observed. Because of the setting of the problem, the observed value $f(x)$ could correspond to two possible inputs: $x$ and $y = x \\oplus s $. Therefore the first register becomes\n",
    "    \n",
    "    $$ \\lvert \\psi_4 \\rangle = \\frac{1}{\\sqrt{2}}  \\left( \\lvert x \\rangle + \\lvert y \\rangle \\right)  $$\n",
    "    \n",
    "    where we omitted the second register since it has been measured.\n",
    "    \n",
    "    </li>\n",
    "    \n",
    "    \n",
    "    \n",
    "    <li> Apply Hadamard on the first register\n",
    "    \n",
    "    $$ \\lvert \\psi_5 \\rangle = \\frac{1}{\\sqrt{2^{n+1}}} \\sum_{z \\in \\{0,1\\}^{n} } \\left[  (-1)^{x \\cdot z} + (-1)^{y \\cdot z} \\right]  \\lvert z \\rangle  $$\n",
    "    \n",
    "    </li>\n",
    "    \n",
    "    <li> Measuring the first register will give an output if:\n",
    "    $$ (-1)^{x \\cdot z} = (-1)^{y \\cdot z} $$\n",
    "    Which means:\n",
    "    $$ x \\cdot z = y \\cdot z \\\\\n",
    "     x \\cdot z = \\left( x \\oplus s \\right) \\cdot z \\\\\n",
    "     x \\cdot z = x \\cdot z \\oplus s \\cdot z \\\\\n",
    "     s \\cdot z = 0$$\n",
    "      \n",
    "    A string $z$ whose inner product with $s$ will be measured.\n",
    "    Thus, repeating the algorithm $\\approx n$ times, one will be able to obtain $n$ different values of $z$ and the following system of equation can be written\n",
    "    \n",
    "    $$ \\begin{cases} s \\cdot z_1 = 0 \\\\ s \\cdot z_2 = 0 \\\\ ... \\\\ s \\cdot z_n = 0 \\end{cases}$$\n",
    "    \n",
    "    From which $s$ can be determined, for example by Gaussian elimination.\n",
    "      \n",
    "    </li>\n",
    "</ol>\n",
    "\n",
    "So, in this particular problem the quantum algorithm performs exponentially fewer steps than the classical one. Once again, it might be difficult to envision an application of this algorithm (although it inspired the most famous algorithm created by Shor) but this represent the first proof that there can be an exponential speed-up in solving a specific problem by using a quantum computer rather than a classical one.\n",
    "\n",
    "### Example\n",
    "\n",
    "Let's see the example of Simon's algorithm for 2 qubits. We take the secret string $s=11$, so that $f(x) = f(y)$ if $y = x \\oplus s$. The state of the qubit register evolves in the following way:\n",
    "\n",
    "<img src=\"figures/5/simon_ex2.jpeg\"  width=\"300\">\n",
    "\n",
    "<ol>\n",
    "    <li> Two $2$-qubit input registers are initialized to the zero state \n",
    "    $$\\lvert \\psi_1 \\rangle = \\lvert 0, 0 \\rangle_1 \\lvert 0, 0 \\rangle_2 $$ </li>\n",
    "    \n",
    "    <li> Apply Hadamard on the first register\n",
    "    $$\\lvert \\psi_2 \\rangle = \\frac{1}{2} \\left( \\lvert 0, 0 \\rangle_1 + \\lvert 0, 1 \\rangle_1 + \\lvert 1, 0 \\rangle_1 + \\lvert 1, 1 \\rangle_1 \\right) \\lvert 0, 0 \\rangle_2 $$ </li>\n",
    "    \n",
    "    <li> For the string $s=11$, the query function can be implemented as $\\text{Q}_f = CX_{13}CX_{14}CX_{23}CX_{24}$, \n",
    "    $$ \\lvert \\psi_3 \\rangle = \\frac{1}{2} \\left( \\lvert 0, 0 \\rangle_1  \\lvert 0\\oplus 0 \\oplus 0, 0 \\oplus 0 \\oplus 0 \\rangle_2 + \\lvert 0 1 \\rangle_1 \\lvert 0\\oplus 0 \\oplus 1, 0 \\oplus 0 \\oplus 1 \\rangle_2 + \\lvert 1 0 \\rangle_1 \\lvert 0\\oplus 1 \\oplus 0, 0 \\oplus 1 \\oplus 0 \\rangle_2 + \\lvert 1 1 \\rangle_1 \\lvert 0\\oplus 1 \\oplus 1, 0 \\oplus 1 \\oplus 1 \\rangle_2 \\right)  $$\n",
    "    \n",
    "    Thus\n",
    "    $$ \\lvert \\psi_3 \\rangle = \\frac{1}{2} \\left( \\lvert 0, 0 \\rangle_1  \\lvert 0, 0 \\rangle_2 + \\lvert 0 1 \\rangle_1 \\lvert 1,  1 \\rangle_2 + \\lvert 1 0 \\rangle_1 \\lvert  1 ,  1  \\rangle_2 + \\lvert 1 1 \\rangle_1 \\lvert 0, 0 \\rangle_2 \\right)  $$\n",
    "    \n",
    "    \n",
    "    </li>\n",
    "    \n",
    "     <li> We measure the second register. With $50\\%$ probability we will see either $\\lvert  0 ,  0  \\rangle_2$ or $\\lvert  1 ,  1  \\rangle_2$. For the sake of the example, let us assume that we see $\\lvert  1 ,  1  \\rangle_2$. The state of the system is then\n",
    "    \n",
    "    $$ \\lvert \\psi_4 \\rangle = \\frac{1}{\\sqrt{2}}  \\left( \\lvert  0 ,  1  \\rangle_1 + \\lvert  1 ,  0  \\rangle_1 \\right)  $$\n",
    "    \n",
    "    where we omitted the second register since it has been measured.\n",
    "    \n",
    "    </li>\n",
    "    \n",
    "    \n",
    "    \n",
    "    <li> Apply Hadamard on the first register\n",
    "    \n",
    "    $$ \\lvert \\psi_5 \\rangle = \\frac{1}{2\\sqrt{2}} \\left[ \\left( \\lvert 0 \\rangle + \\lvert 1 \\rangle \\right) \\otimes \\left( \\lvert 0 \\rangle - \\lvert 1 \\rangle \\right) + \\left( \\lvert 0 \\rangle - \\lvert 1 \\rangle \\right) \\otimes \\left( \\lvert 0 \\rangle + \\lvert 1 \\rangle \\right)  \\right] \\\\\n",
    "    =  \\frac{1}{2\\sqrt{2}} \\left[ \\lvert 0, 0 \\rangle - \\lvert 0, 1 \\rangle + \\lvert 1 0 \\rangle - \\lvert 1 1 \\rangle   + \\lvert 0, 0 \\rangle + \\lvert 0, 1 \\rangle - \\lvert 1 0 \\rangle - \\lvert 1 1 \\rangle \\right] \\\\\n",
    "    = \\frac{1}{\\sqrt{2}} \\left( \\lvert 0, 0 \\rangle - \\lvert 1, 1 \\rangle \\right)$$\n",
    "    \n",
    "    </li>\n",
    "    \n",
    "    <li> Measuring the first register will give either $\\lvert 0, 0 \\rangle$ or $\\lvert 1, 1 \\rangle$ with equal probability. If we see $\\lvert 1, 1 \\rangle$, then:\n",
    "    \n",
    "    $$ s \\cdot 11 = 0 $$\n",
    "    \n",
    "    This is one equation, but $s$ has two variables. Therefore, we need to repeat the algorithm other times to have enough equations that will allow us to determine $s$.\n",
    "      \n",
    "    </li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\"> QISKit: implement the example of Simon algorithm </span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### <span style=\"color:blue\"> 3) Use the query function $Q_f=CX_{13}CX_{14}CX_{23}CX_{24}$ </span>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "List of gates:\n",
      "h\n",
      "h\n",
      "cx\n",
      "cx\n",
      "cx\n",
      "cx\n",
      "measure\n",
      "measure\n",
      "h\n",
      "h\n",
      "measure\n",
      "measure\n",
      "\n",
      "The measured outcomes of the circuits are: {'0000': 256, '0011': 266, '1100': 239, '1111': 263}\n"
     ]
    }
   ],
   "source": [
    "from initialize import *\n",
    "\n",
    "\n",
    "#initialize quantum program\n",
    "my_alg = initialize(circuit_name = 'simon', qubit_number=4, bit_number=4, backend = 'local_qasm_simulator', shots = 1024)\n",
    "\n",
    "#add gates to the circuit\n",
    "\n",
    "my_alg.q_circuit.h(my_alg.q_reg[0]) # applies H gate to first qubit\n",
    "my_alg.q_circuit.h(my_alg.q_reg[1]) # applies H gate to second qubit\n",
    "\n",
    "my_alg.q_circuit.cx(my_alg.q_reg[0],my_alg.q_reg[2]) ## applies CX gate as the query function\n",
    "my_alg.q_circuit.cx(my_alg.q_reg[0],my_alg.q_reg[3]) ## applies CX gate as the query function\n",
    "my_alg.q_circuit.cx(my_alg.q_reg[1],my_alg.q_reg[2]) ## applies CX gate as the query function\n",
    "my_alg.q_circuit.cx(my_alg.q_reg[1],my_alg.q_reg[3]) ## applies CX gate as the query function\n",
    "\n",
    "my_alg.q_circuit.measure(my_alg.q_reg[2], my_alg.c_reg[2]) # measures the third qubit \n",
    "my_alg.q_circuit.measure(my_alg.q_reg[3], my_alg.c_reg[3]) # measures the fourth qubit\n",
    "\n",
    "my_alg.q_circuit.h(my_alg.q_reg[0]) # applies H gate to first qubit\n",
    "my_alg.q_circuit.h(my_alg.q_reg[1]) # applies H gate to second qubit \n",
    "\n",
    "my_alg.q_circuit.measure(my_alg.q_reg[0], my_alg.c_reg[0]) # measures the first qubit\n",
    "my_alg.q_circuit.measure(my_alg.q_reg[1], my_alg.c_reg[1]) # measures the second qubit\n",
    "\n",
    "print('List of gates:')\n",
    "for circuit in my_alg.q_circuit:\n",
    "    print(circuit.name)\n",
    "\n",
    "#Execute the quantum algorithm\n",
    "result = my_alg.Q_program.execute(my_alg.circ_name, backend=my_alg.backend, shots= my_alg.shots)\n",
    "\n",
    "#Show the results obtained from the quantum algorithm \n",
    "counts = result.get_counts(my_alg.circ_name)\n",
    "\n",
    "print('\\nThe measured outcomes of the circuits are:',counts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercises\n",
    "\n",
    "\n",
    "<ol>\n",
    "\n",
    "<li>\n",
    "Show the step-by-step evolution of the state $\\lvert \\psi \\rangle = \\lvert 0 \\rangle$ through the Deutsch algorithm for $ f(0) = 1 $ and $ f(1) = 0$\n",
    "</li>\n",
    "\n",
    "\n",
    "<li>\n",
    "Following the example of Deutsch algorithm given, show the step-by-step evolution of the state $\\lvert \\psi \\rangle = \\lvert 0, 0 \\rangle$ through the Deutsch algorithm where the query function is $\\text{Q}_f = X \\otimes I$\n",
    "\n",
    "</li>\n",
    "\n",
    "<li>\n",
    "Write a QISKit program to run the Deutsch algorithm of problem 2.\n",
    "</li>\n",
    "\n",
    "\n",
    "<li>\n",
    "Consider the Bernstein-Vazirani algorithm for two qubits and one ancilla register, with a query function $\\text{Q}_f = CX_{13}$. What is the secret string $s$ corresponding to $\\text{Q}_f$? \n",
    "</li>\n",
    "\n",
    "\n",
    "<li>\n",
    "Write the step-by-step evolution of the state $\\lvert \\psi \\rangle = \\lvert 0 0 \\rangle \\lvert 1 \\rangle_a$ for problem 4.\n",
    "</li>\n",
    "\n",
    "<li>\n",
    "Write a QISKit program to run the Bernstein-Vazirani algorithm of problem 4.\n",
    "</li>\n",
    "\n",
    "<li>\n",
    "Find the gates needed to realize a query function for Simon's algorithm on two qubits such that the secret string is $s=01$\n",
    "</li>\n",
    "\n",
    "<li>\n",
    "Write the step-by-step evolution of the state $\\lvert \\psi \\rangle = \\lvert 0, 0 \\rangle_1 \\lvert 0, 0 \\rangle_2$ for problem 7.\n",
    "</li>\n",
    "\n",
    "<li>\n",
    "Write a QISKit program to run Simon's algorithm for problem 7.\n",
    "</li>\n",
    "\n",
    "</ol>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "[1] D. Deutsch, Quantum Theory, the Church-Turing Principle and the Universal Quantum\n",
    "Computer, Proc. R. Soc. Lond., Vol. A400, pp. 73{90 (1985).\n",
    "\n",
    "[2]  D. Deutsch, “Quantum computational networks”, Proc. Roy. Soc. Lond. A 425, 73\n",
    "(1989).\n",
    "\n",
    "[3] D. Deutsch, and R. Jozsa, “Rapid solution of problems by quantum computation”,\n",
    "Proceedings of the Royal Society, London, vol. A439, 1992, pp. 553 – 558.\n",
    "\n",
    "[4] R. Gulde, M. Riebe, G.P.T. Lancaster, C. Becher, J. Eschner, H. Haffner and. F. Schmidt-Kaler, I.L. Chuang, and R. Blatt. Implementation of the Deutsch-Jozsa algorithm on an ion-trap quantum computer. Nature, 421:48 (2003).\n",
    "\n",
    "[5] E. Bernstein and U. Vazirani, in Proceedings of the 25th Annual\n",
    "ACM Symposium on the Theory of Computing, ACM, New York, 1993, p. 11.\n",
    "\n",
    "[6] E. Bernstein and U. Vazirani, SIAM J. Comput. 26, 1411 (1997).\n",
    "\n",
    "[7] S. D. Fallek, C. D. Herold, B. J. McMahon, K. M. Maller, K. R. Brown, J. M. Amini, 1,5 Transport implementation of the Bernstein-Vazirani algorithm with ion qubits, New J. Phys. 18 (2016).\n",
    "\n",
    "[8] D. Simon, “On the power of quantum computation”, Proceedings of the 35th Annual\n",
    "Symposium on the Foundations of Computer Science (IEEE Computer Society Press,\n",
    "Los Alamitos, CA, 1994), p. 116."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
